package com.zhanghp.class034;

import com.zhanghp.common.ListNode;

/**
 * 返回两个无环链表相交的第一个节点<br/>
 * 测试链接 : https://leetcode.cn/problems/intersection-of-two-linked-lists/
 *
 * @author zhanghp
 * @since 2024/4/10 17:10
 */
public class Code01_IntersectionOfTwoLinkedLists {


    static class Solution {
        /**
         * <p>
         * 前置知识<br/>
         * 2个相交的链表，2个链表的下一个指针指向同一个链表，所以如果相交，则最后一个节点必定相同
         *
         * @param headA
         * @param headB
         * @return
         */
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) {
                return null;
            }
            ListNode a = headA, b = headB;
            // ==========取出2个链表差的长度===========
            int diff = 0;
            while (a.next != null) {
                a = a.next;
                diff++;
            }
            while (b.next != null) {
                b = b.next;
                diff--;
            }
            // 末尾的空间不相等，则表示无交集
            if (a != b) {
                return null;
            }
            // ========2个链表平齐===========
            if (diff > 0) {
                a = headA;
                b = headB;
            }else {
                a = headB;
                b = headA;
            }
            diff = Math.abs(diff);
            while (diff-- != 0) {
                a = a.next;
            }
            // 寻找交界处
            while (a != b) {
                a = a.next;
                b = b.next;
            }
            return a;
        }
    }
}
